package Algo;

public class BH 
{
	static int arr[];
	static int level = 0;
	public BH (int [] mass)
	{
		arr = mass;
	}
	public static int get_left (int i)
	{
		if (2*i>=arr.length)
			return 0;
		return arr[2*i];
	}
	
	public static int get_right (int i)
	{
		if (2*i+1>=arr.length)
			return 0;
		return arr[2*i+1];
	}
	
	public static int Min_element ()
	{
		return arr[1];
	}
	
	public  static void printBinaryTree() 
	{
		print_binary_tree(1);
	}
	
	
	private static void print_binary_tree (int j)
	{
		for (int i=0; i<level; i++)
			System.out.print ("   ");
		System.out.print (arr [j]);
		level ++;
		if (get_left(j)!=0)
		{	
			System.out.print ("\n");
			for (int i=0; i<level; i++)
				System.out.print ("   ");
			print_binary_tree (2*j);
		}
		if (get_right(j)!=0)
		{
			System.out.print ("\n");
			for (int i=0; i<level; i++)
				System.out.print ("   ");
			print_binary_tree (2*j+1);
		}
		level--;
	}
	
	public static void Insert (int num)
	{
		int i=arr.length-1;
		if (arr[i]!=0)
		makeNewMass();
		else
		{
			while (arr[i]==0)
				{i--;}
		}
		i++;
		arr[i]=num;
		while (arr[(int)(i/2)]>arr[i] && i>1)
		{
			swap ((int)(i/2),i);
			i=(int)(i/2);
		}	
	}
	
	public static void swap ( int a, int b)
	{
		int t=arr[a];
		arr[a]=arr[b];
		arr[b]=t;
	}
	
	public static void makeNewMass ()
	{
		int [] mass = new int [(int)(arr.length*1.3)];
		for (int i=0; i<arr.length; i++)
			mass[i]=arr[i];
		arr=mass;
	}
	
	public static void remove_min ()
	{
		int i = arr.length-1;
		while (arr[i]==0)
			{i--;}
		arr[1]=arr[i];
		arr[i]=0;
		i=1;
		while (arr[i]>get_left(i) && get_left(i)!=0 || arr[i]>get_right(i) && get_right(i)!=0)
		{
			if ((arr[i])>get_left(i) && get_left(i)!=0 && get_left(i)<get_right(i) && get_right(i)!=0)
			{	
				swap (i, 2*i);
				i=2*i;
			}
			else
			{
				swap (i, 2*i+1);
				i=2*i+1;
			}
		}
		
				
	}
	
	public static void main(String[] args) 
	{
		int mass [] = {0,2,3,2,4,5,7,9,6,8,9,11,8,9};
		arr=mass;
		print_binary_tree (1);	
		System.out.print("\n");
		Insert(15);
		Insert(4);
		Insert(19);
		Insert(3);
		Insert(1);
		Insert(-10);
		System.out.print("\n15, 4, 19, 3, 1, -10 have been inserted into the tree: \n");
		printBinaryTree();
		System.out.print("\nMinimum: " + Min_element());
		remove_min();
		System.out.print("\nMinimum has been deleted: \n");
		print_binary_tree (1);
	}

}
